/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/search-for-a-range
   @Language: C++
   @Datetime: 17-03-17 17:09
   */

// Method 1
class Solution {
	/** 
	 *@param A : an integer sorted array
	 *@param target :  an integer to be inserted
	 *return : a list of length 2, [index1, index2]
	 */
public:
	vector<int> searchRange(vector<int> &A, int target) {
		// write your code here
		if (A.size()<1) return {-1,-1};
		int begin=0, end=A.size(), mid;
		while(begin<end){
			mid = (end-begin)/2+begin;
			if (A[mid]>=target) end=mid;
			else begin=mid+1;
		}
		if (end<A.size() && A[end]==target){
			for(begin=end; end<A.size() && A[end]==target; ++end);
			return {begin,end-1};
		}
		return {-1,-1};
	}
};

//Method 2, using stl algorithm
class Solution {
	/** 
	 *@param A : an integer sorted array
	 *@param target :  an integer to be inserted
	 *return : a list of length 2, [index1, index2]
	 */
public:
	vector<int> searchRange(vector<int> &A, int target) {
		// write your code here
		auto begin=lower_bound(A.begin(),A.end(),target);
		if (begin==A.end() || *begin!=target) return {-1,-1};
		auto end=upper_bound(begin,A.end(),target);
		return {begin-A.begin(),end-A.begin()-1};
	}
};
